/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author zhongfang
 *
 */
public class CutOffTreesforGolfEvent {
	static class Node implements Comparable<Node> {
		int x;
		int y;
		int height;

		public Node(int x, int y, int height) {
			this.x = x;
			this.y = y;
			this.height = height;
		}

		@Override
		public int compareTo(Node o) {
			return height - o.height;
		}

	}

	public int cutOffTree(List<List<Integer>> forest) {
		PriorityQueue<Node> cutTreeHight = new PriorityQueue<>();// 堆顶是当前需要砍的树高
		for (int i = 0; i < forest.size(); i++) {
			for (int j = 0; j < forest.get(i).size(); j++) {
				if (forest.get(i).get(j) > 1) {
					cutTreeHight.add(new Node(i, j, forest.get(i).get(j)));
				}
			}
		}
		int[] curPos = { 0, 0 };
		int steps = 0;
		while (!cutTreeHight.isEmpty()) {
			Node node = cutTreeHight.poll();
			int get = getPath(curPos, node, forest);
			if (get == -1) {
				return -1;
			}
			forest.get(node.x).set(node.y, 1);// 变得可以行走
			steps += get;
			curPos[0] = node.x;// 变位置
			curPos[1] = node.y;
		}
		return steps;
	}

	/**
	 * 只能路过1的地方
	 * 
	 * @param curPos
	 * @param node
	 * @param forest
	 * @return
	 */
	private int getPath(int[] curPos, Node node, List<List<Integer>> forest) {
		int[][] neibors = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
		int n = forest.size();
		int m = forest.get(0).size();
		int[][] dp = new int[n][m];
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				dp[i][j] = -1;
			}
		}
		dp[curPos[0]][curPos[1]] = 0;
		int steps = 0;
		int[] target = { node.x, node.y };
		Queue<int[]> posesToDeal = new LinkedList<>();
		posesToDeal.add(curPos);
		while (!posesToDeal.isEmpty()) {
			steps++;
			int curSize = posesToDeal.size();
			for (int i = 0; i < curSize; i++) {
				int[] pos = posesToDeal.poll();
				for (int j = 0; j < neibors.length; j++) {
					int[] next = { pos[0] + neibors[j][0], pos[1] + neibors[j][1] };
					if (next[0] >= 0 && next[0] < n && next[1] >= 0 && next[1] < m
							&& (forest.get(next[0]).get(next[1]) != 0) && dp[next[0]][next[1]] == -1) {// 在矩阵范围内&可以走(1或者当前目标)&没有走过
						dp[next[0]][next[1]] = steps;
						posesToDeal.add(next);
					}
				}
			}
			if (dp[target[0]][target[1]] != -1) {
				return dp[target[0]][target[1]];
			}
		}
		return -1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] nums = { { 54581641, 64080174, 24346381, 69107959 }, { 86374198, 61363882, 68783324, 79706116 },
				{ 668150, 92178815, 89819108, 94701471 }, { 83920491, 22724204, 46281641, 47531096 },
				{ 89078499, 18904913, 25462145, 60813308 } };
		List<List<Integer>> arrayList = new ArrayList<>();
		for (int i = 0; i < nums.length; i++) {
			ArrayList<Integer> list = new ArrayList<>();
			for (int j = 0; j < nums[0].length; j++) {
				list.add(nums[i][j]);
			}
			arrayList.add(list);
		}
		System.out.println(new CutOffTreesforGolfEvent().cutOffTree(arrayList));
	}

}
